ABSTRACT

This thesis addresses the problems of managing the transmissions of stations in a spread-spectrum packet radio network so that the system can remain effective when scaled to millions of nodes concentrated in a metropolitan area. The principal diffi- culty in scaling a system of packet radio stations is interference from other stations in the system. Interference comes both from nearby stations and from distant stations. Each nearby interfering station is a particular problem, because a signal received from it may be as strong as or stronger than the desired signal from some other station. Far-off interfering stations are not individually a problem, since each of their signals will be weaker, but the combined effect may be the dominant source of interference. The thesis begins with an analysis of propagation and interference models. The overall noise level in the system (mainly caused by the many distant stations) is then analyzed, and found to remain manageable even as the system scales to billions of nodes. A scheme for designing a scalable packet radio network is then presented. Included is a method of scheduling packet transmissions to avoid collisions (caused by interference from nearby stations) without the need for global coordination or synchronization. Simulations of a system of one thousand stations are used to verify and illustrate the methods used.

A method of choosing routes (minimum-energy routes) is demonstrated in simu- lation to produce a fully connected and functional network for one hundred and one thousand randomly placed stations. Unfortunately, congestion as the system scales is unavoidable if the traffic is not limited to some degree of locality. If traffic is limited to a few hops, then for a large system the techniques presented in this thesis are superior to ideal time division multiplexing of a clear channel.